package 排序;

import java.util.Arrays;

public class 归并排序 {
    public static int[] mergeSort(int[] arr) {
        if (arr==null || arr.length<2) {
            return arr;
        }
        process(arr,0,arr.length-1);
        return arr;
    }

    private static void process(int[] arr, int left, int right) {
        if (left==right) {
            return;
        }
        int mid=left+((right-left)>>1);
        process(arr,left,mid);
        process(arr,mid+1,right);
        merge(arr,left,mid,right);

    }

    private static void merge(int[] arr, int left, int mid,int right) {
        int[] help=new int[right-left+1];
        int p1=left;
        int p2=mid+1;
        int i=0;

        while (p1<=mid && p2<=right) {
            help[i]= arr[p1]<=arr[p2] ? arr[p1++]:arr[p2++];
            i++;
        }

        while (p1<=mid) {
            help[i++]=arr[p1++];
        }
        while (p2<=right) {
            help[i++]=arr[p2++];
        }
        for (int j = 0; j <help.length; j++) {
            arr[left+j]=help[j];
        }
    }

    public static void main(String[] args) {
        int [] arr={2,7,5,2,3,4,1};
        System.out.println(Arrays.toString(mergeSort(arr)));
    }
}
